package LeetCode;

import java.util.Arrays;

/**
 * @Author: Dijah
 * @Date: 2023/1/3 16:43
 * @Desc:
 * 给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。
 * 计算并返回可以凑成总金额所需的 最少的硬币个数 。 如果没有任何一种硬币组合能组成总金额，返回 -1 。
 */
public class code322_coinsChange {

    public static int coinChange(int[] coins,int amount){
        //暴力递归
        if(coins == null || coins.length == 0){
            return 0;
        }
        int [] dp = new int[amount + 1];
        Arrays.fill(dp, amount + 1);
        //填充
        dp[0] = 0;
        for(int i = 0; i < dp.length; i++){
            for(int coin : coins){
                if(i -coin < 0){
                    continue;
                }
                dp[i] = Math.min(dp[i],1 + dp[i-coin]);

            }
        }
        return (dp[amount] == amount + 1) ? -1 : dp[amount];
    }

    public static void main(String[] args) {
        int [] coins = {4,3,5};
        int amount = 11;
        int i = coinChange(coins, amount);
        System.out.println(i);
    }
}
